package com.jiang.专题.数组.Q55;

/**
 * @author Jiang
 * @version 1.0
 * @date 2024/12/16 22:38
 */
class Solution {
    // 贪心算法
    public boolean canJump(int[] nums) {
        // int len = nums.length;
        // int right = 0; // 能跳到的位置
        // for (int i = 0; i < len; i++) {
        //     if (i <= right) {
        //         right = Math.max(right, i + nums[i]);
        //         if (right >= len - 1) return true;
        //     } else {
        //         return false;
        //     }
        // }
        // return false;

        // 对上面代码简化
        int len = nums.length;
        int right = 0; // 能跳到的位置
        for (int i = 0; i <= right; i++) {
            right = Math.max(right, i + nums[i]);
            if (right >= len - 1) return true;
        }
        return false;
    }

    // 动态规划
    // public boolean canJump(int[] nums) {
    //     int len = nums.length;
    //     // 创建一个数组，数组的每一个元素值表示是否已经跳跃
    //     boolean[] done = new boolean[len];
    //     // 调用动态规划方法
    //     dp(nums, done, 0, len);
    //     return done[len - 1];
    // }

    // public void dp(int[] nums, boolean[] done, int cur, int len) {
    //     // 设置当前位置已跳跃
    //     done[cur] = true;
    //     // 如果能成功跳跃到最后位置，则返回
    //     if (done[len - 1]) return;
    //     // 遍历能跳跃的长度
    //     for (int i = 1; i <= nums[cur]; i++) {
    //         // 方法回溯时，如果能成功跳跃到最后位置
    //         if (done[len - 1]) return;
    //         // 跳跃后的位置
    //         int temp = cur + i;
    //         // 如果跳跃超过最后位置，则返回
    //         if (temp >= len) return;
    //         // 如果没有跳跃，则递归
    //         if (!done[temp]) {
    //             dp(nums, done, cur + i, len);
    //         }
    //     }
    // }

}
